1. Field of the Invention
The present invention relates to error detection in data communication.
2. Description of the Related Art
An error detection code is a value indicative of a change in a data field. The cyclic redundancy check (CRC) is an error-detection method based on a transformation of the bit pattern in a data message (e.g., a packet, frame or cell). The basic idea of CRC algorithms is simply to treat the message as a binary number, to divide it by another fixed binary number, and to append the remainder from this division onto the end of the message. The remainder is the error detection code. The quotient is not used in CRC error detection. The divisor is a polynomial whose order depends on the number of bits allocated for the remainder, and is typically referred to as the generating polynomial.
CRC calculations can be computationally intensive, especially with longer messages. In situations where the message length is fixed and where high speed is desired, CRCs are often computed using look-up tables. Look-up tables are used in these situations to ease the computations at the expense of more memory.
Use of CRC in error detection has six basic steps. First, the sender computes a CRC value. Second, the send appends this CRC value to the data message. Third, the sender sends the error-encoded data message. Fourth, the receiver receives the error-encoded message. Fifth, the receiver computes a CRC value based on the data portion of the received packet. Sixth, the receiver compares his CRC value with the sender's CRC value in the error-encoded message. If the two match, there is a high probability that the message has been received without error. The probability is high enough that undetected errors must involve more than two bits in the message, and will generally be recognized through other means. It should be noted that as an alternative to the fifth step, a binary checksum may be computed on the entire error-encoded data.
CRCs are commonly used for error correction in asynchronous transfer mode (ATM) networks. ATM networks are packet-switched, and the applicable specifications provide several cell types. ATM cells are 53 bytes, consisting of a 5 byte header and 48 bytes of information. In addition to ATM networks, CRCs are commonly used for error correction in other networks. For example, forms of CRC-16 are used in X.25, SDLC/HDLC and XMODEM communications. Forms of CRC-32 are used in Ethernet networks, PKZIP compression and FDDI networks.
ATM networks include system management functions to achieve efficient internal operation. Included within system management are a number of functions grouped together as “operations and maintenance” (OAM). OAM includes fault management, performance management, configuration management, accounting management, security management and traffic management. These functions generally operate independently and according to defined procedures. OAM cells can be generated, inserted, processed, monitored, routed and terminated at various points in an ATM network.
One type of ATM cell is the OAM cell. FIG. 1A shows the format of an OAM cell 100. The OAM cell 100 includes a 5-byte header 110 (like all ATM cells) and 48 bytes of payload 170 consisting of a 4-bit OAM cell type 120, a 4-bit function type 130, a 45-byte function specific field 140, a 6-bit reserved space 150 and a 10-bit error detection code (EDC) field 160. OAM fault management cells are used for alarm surveillance, continuity checks and loopback testing.
Error detection codes such as that in the EDC field 160 help in detection of whether the payload has been corrupted during transmission of the respective data message. The EDC field 160 is a CRC-10 error detection code using the generating polynomial X10+x9+x5+x4+x+1 (i.e., the modulo-2 divisor 11000110011). The CRC-10 is computed from the payload 170 (except for the EDC field 160). Ordinarily, to compute a CRC-10 of the 48-byte payload, a processor will need a 256 byte look-up table (stored in RAM) and about 48×N instructions or operations, where N is the number of instructions (approximately 12 for an Intel 8051 micro-controller) or operations needed to compute the CRC-10 on one byte. It can be seen that CRC computation can be a significant load, especially in embedded systems that employ slow microprocessors.
ATM communications are carried along virtual channels (VCs). Where greater bandwidth is needed for a given communication session than is available in a single VC, several VCs may be bundled into a virtual path (VP) The end-to-end arrangement of a VC or VP is called a connection, meaning that ATM communications are actually carried on virtual channel connections (VCCs) or virtual path connections (VPCs).
ATM operations and management provides many ways to test and control VCCs and VPCs. Loopback is a fault management function for testing the integrity of the connections within a VCC or VPC. The loopback function is useful for locating faults in a VCC or VPC. Loopback can also be used to measure round-trip cell transfer delays. In the loopback test, an OAM cell is inserted at some point into a VCC or VPC. When the cell reaches the endpoint of the VCC or VPC, the endpoint loops the OAM cell back (i.e., is returned in the reverse flow of the VC or VP).
The layout of a loopback cell is specified. The cell type 120 is 0001, indicating an OAM cell. The function type 130 of a loopback cell is 1000. FIG. 1B shows the format of the function specific field 140. The function specific field 140 includes a 1-byte loopback indication field 141, a 4-byte correlation tap 142, a 15-byte loopback location field 143, a 15-byte source ID field 144, and 10-bytes of unused space 145. The loopback indication field 141 signifies whether loopback has occurred. The least significant bit of the loopback indication field 141 (“the loopback indication bit”) is initially set to 1. Upon loopback, the loopback indication bit is reset to 0, indicating that the cell has been looped back. The correlation tag 142 identifies (correlates) related OAM cells within the same connection and uniquely identifies the cell. The loopback location field 143 is an optional field that identifies the point for loopback. The source ID field 144 is an optional field that allows the originator to identify its own cells.
ATM specification have been improved to permit higher speeds and greater bandwidths. Although processing efficiency has always been important to peak ATM operations, higher speeds and greater bandwidths place ever greater demands on cell processing.